class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        // 记忆化搜索
        // dfs(i) 表示完成 days[i] 的最小花费
        // 从后往前遍历
        vector<int> memo(366, -1);      // 记忆化搜索
        int day[3] = {1, 7, 30};
        auto dfs = [&](this auto &&dfs, int i)->int
        {
            if(i < 0)
                return 0;   // 走完了，返回 0
            
            if(memo[i] != -1)
                return memo[i];
            
            // 遍历三种票价
            int res = INT_MAX;      // 初始化完成该天旅行的最小花费
            for(int j = 0; j < 3; j++)
            {
                // 计算可以在哪一天买票，从而包含 i 这一天
                // 如果是买了为期一天的票，起始天数就是 days[i] - 1 + 1
                // 如果是买了为期七天的票，起始天数就是 days[i] - 7 + 1
                // ...
                int start = days[i] - day[j] + 1;

                // 计算下一个递归的入口，算一下是哪天
                int idx = i;
                while(idx >= 0 && days[idx] >= start)
                    idx--;
                
                // 出上面的while循环有两种情况
                // 1. days[idx] < start，说明买了 j 这个票，为期 day[j] 天包含不住这一天，表明这一天需要重新买票
                // 2. idx == -1，说明买了 j 这个票，可以全都覆盖了，不用递归了
                res = min(res, costs[j] + ((idx == -1) ? 0 : dfs(idx)));
            }
            return memo[i] = res;
        };
        // return dfs(days.size() - 1);

        // 翻译成递归
        int n = days.size();
        vector<int> f(n + 1);
        int j = 0, k = 0;
        for (int i = 0; i < n; i++)
        {
            int d = days[i];
            while (days[j] <= d - 7)
                j++;

            while (days[k] <= d - 30)
                k++;

            f[i + 1] = min({f[i] + costs[0], f[j] + costs[1], f[k] + costs[2]});
        }
        return f[n];

    }
};